/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2024-11-21
 * @Description: Cg动态规划练习之01背包
 *******************************************************************************/
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int knapsack(const vector<int>& prices, const vector<int>& volumes, int total_volume)
{
    int n = prices.size();
    vector<vector<int>> dp(n + 1, vector<int>(total_volume + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= total_volume; ++j)
        {
            // prices和volumes与dp同一个商品序号相差1
            if (j >= volumes[i - 1] && prices[i - 1] + dp[i - 1][j - volumes[i - 1]] > dp[i - 1][j])
                dp[i][j] = prices[i - 1] + dp[i - 1][j - volumes[i - 1]];
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[n][total_volume];
}

int main()
{
    string line;
    getline(cin, line);
    size_t semicolonPos = line.find(';');
    int totalVolume = stoi(line.substr(0, semicolonPos));
    string goods = line.substr(semicolonPos + 1);
    stringstream ss(goods);
    string segment;
    vector<int> prices, volumes;
    while (getline(ss, segment, ';'))
    {
        if (!segment.empty())
        {
            size_t commaPos = segment.find(',');
            volumes.push_back(stoi(segment.substr(0, commaPos)));
            prices.push_back(stoi(segment.substr(commaPos + 1)));
        }
    }

    cout << knapsack(prices, volumes, totalVolume);
    return 0;
}

/*
Test Case
10;3,50;5,20;1,10;2,30;7,70;
*/
